import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

import soot.Body;
import soot.Scene;
import soot.SootClass;
import soot.SootMethod;
import soot.Unit;
import soot.jimple.toolkits.callgraph.CallGraph;
import soot.jimple.toolkits.callgraph.Targets;
import soot.tagkit.LineNumberTag;
import soot.tagkit.Tag;
import soot.toolkits.graph.BriefUnitGraph;
import soot.toolkits.graph.UnitGraph;

public class IndexGenerator {
	/**
	 * the container of all the methods
	 */
	private Vector<IndexMethod> methods;
	
	/**
	 * the classNames from the file types_and_compliationUnits.txt
	 */
	Vector<String> files;
	
	/**
	 * the call graph
	 */
	private CallGraph cg;

	public IndexGenerator() {
		methods = new Vector<IndexMethod>();
	}

	public IndexGenerator(CallGraph cg) {
		methods = new Vector<IndexMethod>();
		this.cg = cg;
	}

	public IndexGenerator(CallGraph cg, Vector<String> files) {
		methods = new Vector<IndexMethod>();
		this.files = files;
		this.cg = cg;
	}

	public Vector<IndexMethod> getMethods() {
		return this.methods;
	}

	/**
	 * initialize all the index of the current methods
	 */
	public void init() {
		Vector<ClassName> classes = ClassNameIndex.getAllClasses();
		// loop among classes
		for (int i = 0; i < classes.size(); i++) {
			// if the class is not used in the current project, skip it.
			if (!Scene.v().containsClass(classes.get(i).className)) {
				continue;
			}
			SootClass s = Scene.v().loadClassAndSupport(
					classes.get(i).className);
			s.setApplicationClass();
			
			Iterator methodIt = s.getMethods().iterator();
			// loop among mehthods in specific class
			while (methodIt.hasNext()) {
				IndexMethod method = new IndexMethod();
				SootMethod m = (SootMethod) methodIt.next();
				// skip abstract part of the class
				// FIXME: the <clinit> and <init> methods may be meaningful in our analysis.
				// Further investigation is needed.
				if (m.getName().equals("<clinit>")
						|| m.getName().equals("<init>") || !m.isConcrete()) {
					continue;
				}
				method.setName(m.toString());
				Body b = m.retrieveActiveBody();
				
				// Get the CFG of the method
				UnitGraph g = new BriefUnitGraph(b);
				int classNum = ClassNameIndex.getClassNum(m.getDeclaringClass()
						.toString());
				// here get the paths from the unit graph
				System.out.print(method.getName());
				// process it, get all the basic paths from the method.
				// Basic path means all the nodes of one path belong to the same
				// method, or the path has not been extended
				processMethod(classNum, g, cg, method, false);
				System.out.println("all " + method.size() + " paths finish!");
				methods.add(method);
			}
		}
	}

	/**
	 * the main part of the index generator.
	 * Analyze the intra-procedural control flow graph for a given method
	 * to enumerate all the acyclic static paths in this method.
	 * 
	 * @param classNum
	 *            the number of the class according to file
	 *            types_and_complicationUnits.txt
	 * @param g
	 *            the unit graph of the method
	 * @param cg
	 *            the call graph of the project
	 * @param method
	 *            the method to be fullfilled
	 */
	private void processMethod(int classNum, UnitGraph g, CallGraph cg,
			IndexMethod method, boolean countingMode) {
		long numPathInMethod = 0L;
		List temp = g.getHeads();
		Unit currentUnit = (Unit) temp.get(0);

		Stack<IndexPath> otherPath = new Stack<IndexPath>();
		IndexPath firstPath = new IndexPath();
		String line = currentUnit.getTags().get(0).toString();
		String firstValue = classNum + "::" + line;
		// add the start point of the method
		firstPath.addNode(new IndexNode(firstValue, currentUnit, true));

		// add the first path
		otherPath.add(firstPath);

		IndexPath currentPath;
		IndexNode currentNode;

		while (!otherPath.empty()) {
			currentPath = otherPath.pop();
			currentNode = currentPath.getLast();
			currentUnit = currentNode.getUnit();

			boolean finish = false;
			while (!finish) {
				List succs = g.getSuccsOf(currentUnit);
				if (succs.size() == 0) {
					// finish one path,not success nodes
					if(countingMode){
						currentPath = null; // leave the current path object to gc to reduce memory consumption
						numPathInMethod = numPathInMethod + 1L;
					}else{
						method.addPath(currentPath);
					}
					finish = true;
				} else {
					if (succs.size() == 1) {
						// just one success node, add it. and I am sure there
						// will never be duplicated unit when there is only one
						// success node, for it will cause a dead lock
						Unit unit = (Unit) succs.get(0);
						int lineNum = getLineFromUnit(unit);
						String val = classNum + "::" + lineNum;
						IndexNode node = new IndexNode(val, unit, true);
						boolean isCallPoint = isCallPoint(unit, cg, g,
								currentPath);
						node.setIsLeaff(!isCallPoint);
						// if the current path already has the value, we shall
						// not record it twice however we must otherwise add it
						// for it may be a call point or has success nodes
						if (currentPath.contains(val)) {
							node.setShouldRecord(false);
						}
						currentPath.addNode(node);
						currentNode = node;
						currentUnit = unit;
					} else {
						for (int i = 0; i < succs.size(); i++) {
							Unit unit = (Unit) succs.get(i);
							// whether contains a duplicated unit, if so just
							// skip it
							if (currentPath.contains(unit)) {
								continue;
							}
							int lineNum = getLineFromUnit(unit);
							String val = classNum + "::" + lineNum;
							IndexNode node = new IndexNode(val, unit, true);
							boolean isCallPoint = isCallPoint(unit, cg, g,
									currentPath);
							node.setIsLeaff(!isCallPoint);
							if (currentPath.contains(val)) {
								node.setShouldRecord(false);
							}
							IndexPath path = currentPath.clone();
							path.addNode(node);
							// add it to stack
							otherPath.add(path);
						}
						finish = true;
					}
				}
			}
		}
		
		if(countingMode){
			System.out.println("***NUMBER OF PATHS***: " + numPathInMethod);
		}else{
			if (method.size() == 0) {
				// one method has no path? I would rather this line will never
				// reach....
				System.out.println("!!somethine wrong here! method size is 0!!!");
			}
		}
	}

	/***
	 * check if the current unit has been called before
	 * 
	 * @param _u
	 * @param _cg
	 * @param _g
	 * @param path
	 * @return whether the unit has been called before
	 */
	public boolean isCallPoint(Unit _u, CallGraph _cg, UnitGraph _g,
			IndexPath path) {
		final String[] ALLCLASS = new String[files.size()];
		files.toArray(ALLCLASS);
		Iterator targets = new Targets(_cg.edgesOutOf(_u));
		while (targets.hasNext()) {
			SootMethod smethod = (SootMethod) targets.next();
			if (smethod.getName().equals("<clinit>")
					|| smethod.getName().equals("<init>")) {
				continue;
			}
			String cm = smethod.getDeclaringClass().toString();
			if (path.isCalled(smethod.toString())) {
				return false;
			}
			for (int i = 0; i < ALLCLASS.length; i++) {
				if (cm.equals(ALLCLASS[i])) {
					path.called(smethod.toString());
					return true;
				}
			}
		}
		return false;
	}

	@Override
	public String toString() {
		System.out.println("there are all " + methods.size() + " methods");
		StringBuffer sb = new StringBuffer("");
		for (int i = 0; i < methods.size(); i++) {
			sb.append(methods.get(i).toString() + "\n\n");
		}
		return sb.toString();
	}

	private int getLineFromUnit(Unit unit) {
		for (Iterator j = unit.getTags().iterator(); j.hasNext();) {
			Tag tag = (Tag) j.next();
			if (tag instanceof LineNumberTag) {
				// byte[] value = tag.getValue();
				// int lineNumber = ((value[0] & 0xff) << 8) | (value[1] &
				// 0xff);
				LineNumberTag lnTag = (LineNumberTag) tag;
				int lineNumber = lnTag.getLineNumber();
				return lineNumber;
			}
		}
		return -1;
	}
}
